package algorithms.leaning.class13;

import common.bean.multiple.TreeNode;

/**
 * 派对的最大快乐值
 * <p>
 * 公司的每个员工都符合 Employee 类的描述。
 * 整个公司的人员结构可以看作是一棵标准的、 没有环的多叉树。
 * 树的头节点是公司唯一的老板。除老板之外的每个员工都有唯一的直接上级。
 * 叶节点是没有任何下属的基层员工(subordinates列表为空)，
 * 除基层员工外，每个员工都有一个或多个直接下级。
 * <p>
 * 这个公司现在要办party，你可以决定哪些员工来，哪些员工不来，规则如下：
 * 1.如果某个员工来了，那么这个员工的所有直接下级都不能来
 * 2.派对的整体快乐值是所有到场员工快乐值的累加
 * 3.你的目标是让派对的整体快乐值尽量大
 * 给定一棵多叉树的头节点boss，请返回派对的最大快乐值。
 *
 * @author guichang
 * @date 2021/6/13
 */

@SuppressWarnings("all")
public class Code3_二叉树_快乐值 {
    // 1、头节点来的情况，直接子节点必须不来的最大快乐值
    // 2、头节点不来的情况，直接子节点可来可不来的最大快乐值

    public static int maxHappy(TreeNode head) {
        Info info = process(head);
        return Math.max(info.yes, info.no);
    }

    private static Info process(TreeNode node) {
        if (node == null) {
            return new Info(0, 0);
        }
        int yes = node.val;
        int no = 0;
        for (TreeNode n : node.children) {
            Info info = process(n);
            yes += info.no; // head来的话子节点必须不能来
            no += Math.max(info.yes, info.no); // head不来的话子节点可来可不来
        }
        return new Info(yes, no);
    }

    private static class Info {
        int yes; // 我来的最大快乐值
        int no; // 我不来的最大快乐值

        public Info(int yes, int no) {
            this.yes = yes;
            this.no = no;
        }
    }

}